{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Score Triangulation of Polygon"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minScoreTriangulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #多边形三角剖分的最低得分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一个凸的<meta charset=\"UTF-8\" />&nbsp;<code>n</code>&nbsp;边形，其每个顶点都有一个整数值。给定一个整数数组<meta charset=\"UTF-8\" />&nbsp;<code>values</code>&nbsp;，其中<meta charset=\"UTF-8\" />&nbsp;<code>values[i]</code>&nbsp;是第 <code>i</code> 个顶点的值（即 <strong>顺时针顺序</strong> ）。</p>\n",
    "\n",
    "<p>假设将多边形 <strong>剖分</strong>&nbsp;为 <code>n - 2</code>&nbsp;个三角形。对于每个三角形，该三角形的值是顶点标记的<strong>乘积</strong>，三角剖分的分数是进行三角剖分后所有 <code>n - 2</code>&nbsp;个三角形的值之和。</p>\n",
    "\n",
    "<p>返回 <em>多边形进行三角剖分后可以得到的最低分</em> 。<br />\n",
    "&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/25/shape1.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>values = [1,2,3]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>多边形已经三角化，唯一三角形的分数为 6。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/25/shape2.jpg\" style=\"height: 163px; width: 446px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>values = [3,7,4,5]\n",
    "<strong>输出：</strong>144\n",
    "<strong>解释：</strong>有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/25/shape3.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>values = [1,3,1,4,1,5]\n",
    "<strong>输出：</strong>13\n",
    "<strong>解释：</strong>最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == values.length</code></li>\n",
    "\t<li><code>3 &lt;= n &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= values[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-score-triangulation-of-polygon](https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-score-triangulation-of-polygon](https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[3,7,4,5]', '[1,3,1,4,1,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, v: List[int]) -> int:\n",
    "        n = len(v)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 3, -1, -1):\n",
    "            for j in range(i + 2, n):\n",
    "                f[i][j] = min(f[i][k] + f[k][j] + v[i] * v[j] * v[k]\n",
    "                              for k in range(i + 1, j))\n",
    "        return f[0][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+2, n):\n",
    "                f[i][j] = inf\n",
    "                for k in range(i+1, j):\n",
    "                    f[i][j] = min(f[i][j], f[i][k] + f[k][j] + values[i]*values[j]*values[k])\n",
    "        return f[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "每一步，可以任意选择一个三角形i,j,k\n",
    "枚举k\n",
    "f[i][j]=f[i][k]+f[k][j]+c\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n=len(values)\n",
    "        # @cache    \n",
    "        # def dfs(i:int,j:int)->int:\n",
    "        #     if i+1==j:\n",
    "        #         return 0\n",
    "        #     ans=inf\n",
    "        #     for k in range(i+1,j):\n",
    "        #         c=values[i]*values[j]*values[k]\n",
    "        #         ans=min(ans,c+dfs(i,k)+dfs(k,j))\n",
    "        #     return ans\n",
    "        # return dfs(0,n-1)\n",
    "\n",
    "        f=[[0]*n for _ in range(n)]\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+2,n):\n",
    "                f[i][j]=min(f[i][k]+f[k][j]+values[i]*values[j]*values[k] for k in range(i+1,j))\n",
    "        return f[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        '''\n",
    "        dp[i][j]表示从定点i顺时针到顶点j，这样划分出来的最小得分；\n",
    "        枚举从i+1到j-1的k，子问题是dp[i][k]和dp[k][j]\n",
    "        dp[i][j] = min^ {j-1}_{i+1}(dp[i][k]+dp[k][j]+v[i]*v[k]*v[j])\n",
    "        边界条件：i+1==j时说明没有三角形，是0  \n",
    "        在用递推写的时候，dp[i]从dp[k]转移来所以i倒序；dp[j]从dp[k]转移来所以j正序\n",
    "        '''\n",
    "        # n = len(values)\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i + 1 == j:\n",
    "        #         return 0\n",
    "        #     ans = float('inf')\n",
    "        #     # 枚举k\n",
    "        #     for k in range(i + 1, j):\n",
    "        #         ans = min(ans, dfs(i, k) + dfs(k, j) + values[i] * values[k] * values[j])\n",
    "        #     return ans\n",
    "        # return dfs(0, n - 1)\n",
    "\n",
    "        n = len(values)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        # 枚举i时，j至少是i+2，所以从n-3开始\n",
    "        for i in range(n - 3, -1, -1):\n",
    "            for j in range(i + 2, n):\n",
    "                ans = float('inf')\n",
    "                for k in range(i + 1, j):\n",
    "                    ans = min(\n",
    "                        ans,\n",
    "                        dp[i][k] + dp[k][j] + values[i] * values[k] * values[j],\n",
    "                    )\n",
    "                dp[i][j] = ans\n",
    "\n",
    "        return dp[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i + 1 == j:\n",
    "        #         return 0\n",
    "        #     res = inf\n",
    "        #     for k in range(i+1, j):\n",
    "        #         res = min(res, dfs(i, k) + dfs(k, j) + values[i] * values[j] * values[k])\n",
    "        #     return res\n",
    "        # return dfs(0, n-1)\n",
    "\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+2, n):\n",
    "                res = inf\n",
    "                for k in range(i+1, j):\n",
    "                    res = min(res, f[i][k] + f[k][j] + values[i] * values[j] * values[k])\n",
    "                f[i][j] = res\n",
    "        return f[0][n-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "\n",
    "        # def dfs(i, j):\n",
    "        #     if i+1 == j:\n",
    "        #         return 0\n",
    "        #     res = inf\n",
    "        #     for k in range(i+1, j):\n",
    "        #         res = min(res, dfs(i,k)+dfs(k,j)+values[i]*values[j]*values[k])\n",
    "        #     return res\n",
    "        # return dfs(0, n-1)\n",
    "\n",
    "        f = [[0]*n for _ in range(n)]\n",
    "        for i in range(n-3, -1, -1):\n",
    "            for j in range(i+2, n):\n",
    "                res = inf\n",
    "                for k in range(i+1, j):\n",
    "                    res = min(res, f[i][k]+f[k][j]+values[i]*values[j]*values[k])\n",
    "                f[i][j] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "dfs(i,j)\n",
    "\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-3,-1,-1):  # 倒序遍历 i\n",
    "            for j in range(i+2, n):\n",
    "                res = inf\n",
    "                for k in range(i+1, j):\n",
    "                    res = min(res, f[i][k] + f[k][j] + values[i] * values[j] * values[k])\n",
    "                f[i][j] = res\n",
    "        return f[0][-1]\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i+1 == j:\n",
    "        #         return 0\n",
    "        #     res = inf\n",
    "        #     for k in range(i+1, j):\n",
    "        #         res = min(res, dfs(i, k) + dfs(k, j) + values[i] * values[j] * values[k])\n",
    "        #     return res\n",
    "        #return dfs(0, len(values)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 3, -1, -1):\n",
    "            for j in range(i + 2, n):\n",
    "                f[i][j] = min(f[i][k] + f[k][j] + values[i] * values[j] * values[k] \n",
    "                for k in range(i + 1, j))\n",
    "        return f[0][n - 1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 3, -1, -1):\n",
    "            for j in range(i + 2, n):\n",
    "                res = inf\n",
    "                for k in range(i + 1, j):\n",
    "                    res = min(res, f[k][j] + f[i][k] + values[i] * values[k] * values[j])\n",
    "                f[i][j] = res\n",
    "        return f[0][n - 1]\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i + 1 == j:\n",
    "        #         return 0\n",
    "        #     res = inf\n",
    "        #     for k in range(i + 1, j):\n",
    "        #         res = min(res, dfs(k, j) + dfs(i, k) + values[i] * values[k] * values[j])\n",
    "        #\n",
    "        #     return res\n",
    "        #\n",
    "        # return dfs(0, n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n=len(values)\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i+1==j:\n",
    "        #         return 0\n",
    "        #     res=inf \n",
    "        #     for k in range(i+1,j):\n",
    "        #         res=min(res,dfs(i,k)+dfs(k,j)+values[i]*values[j]*values[k])\n",
    "        #     return res \n",
    "        # return dfs(0,n-1)\n",
    "        dp=[[0]*n for _ in range(n)]\n",
    "        for i in range(n-3,-1,-1):\n",
    "            for j in range(i+2,n):\n",
    "                res=inf \n",
    "                for k in range(i+1,j):\n",
    "                    res=min(res,dp[i][k]+dp[k][j]+values[i]*values[j]*values[k])\n",
    "                dp[i][j]=res \n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "\n",
    "        n = len(values)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for l in range(n-3,-1,-1):\n",
    "            for r in range(l+2,n):\n",
    "                dp[l][r] = float('inf')\n",
    "                for m in range(l+1,r):\n",
    "                    dp[l][r] = min(dp[l][r],dp[l][m]+dp[m][r]+values[l]*values[r]*values[m])\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for l in range(n - 3, -1, -1):\n",
    "            for r in range(l + 2, n):\n",
    "                dp[l][r] = inf\n",
    "                for k in range(l + 1, r):\n",
    "                    dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r] + values[l] * values[k] * values[r])\n",
    "        return dp[0][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, v: List[int]) -> int:\n",
    "        n = len(v)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 3, -1, -1):\n",
    "            for j in range(i + 2, n):\n",
    "                f[i][j] = min(f[i][k] + f[k][j] + v[i] * v[j] * v[k] for k in range(i + 1, j))\n",
    "        return f[0][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for gap in range(2, n):\n",
    "            for i in range(n - gap):\n",
    "                j = i + gap\n",
    "                dp[i][j] = float('inf')\n",
    "                for k in range(i + 1, j):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j])\n",
    "        \n",
    "        return dp[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        # 递推\n",
    "        # f[i][j] = min(f[i][j], f[i][k] + f[k][j] + values[i] * values[j] * values[k])\n",
    "        n = len(values)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        \n",
    "        for i in range(n - 3, -1, -1):\n",
    "            for j in range(i + 2, n):\n",
    "                res = inf\n",
    "                for k in range(i + 1, j):\n",
    "                    res = min(res, f[i][k] + f[k][j] + values[i] * values[j] * values[k])\n",
    "                f[i][j] = res\n",
    "        \n",
    "        return f[0][n - 1]\n",
    "\n",
    "        # 记忆化搜索\n",
    "        # n = len(values)\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i: int, j: int) -> int:\n",
    "        #     if i + 1 == j:\n",
    "        #         return 0\n",
    "            \n",
    "        #     res = inf\n",
    "        #     for k in range(i + 1, j):\n",
    "        #         res = min(res, dfs(i, k) + dfs(k, j) + values[i] * values[j] * values[k])       \n",
    "        #     return res\n",
    "        # return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, v: List[int]) -> int:\n",
    "        \n",
    "        n = len(v)\n",
    "        f = [[0]*n for _ in range(n)]\n",
    "        for i in range(n-3,-1,-1):\n",
    "            for j in range(i+2,n):\n",
    "                res = inf\n",
    "                for k in range(i+1,j):\n",
    "                    res = min(res,f[i][k]+f[k][j]+v[i]*v[k]*v[j])\n",
    "                f[i][j] = res\n",
    "        return f[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        #区间DP\n",
    "        n=len(values)\n",
    "        dp=[[inf]*n for _ in range(n)]\n",
    "        #初始化\n",
    "        for i in range(1,n):\n",
    "            dp[i-1][i]=0\n",
    "        #枚举区间长度\n",
    "        for length in range(2,n+1):\n",
    "            #枚举起点\n",
    "            for i in range(n-length+1):\n",
    "                #得到终点\n",
    "                j=i+length-1\n",
    "                #枚举中间分割点k\n",
    "                for k in range(i+1,j):\n",
    "                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+values[i]*values[j]*values[k])\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 3, -1, -1):\n",
    "            f[i][i + 1] = 0\n",
    "            for j in range(i + 2, n):\n",
    "                res = inf\n",
    "                for k in range(i + 1, j):\n",
    "                    res = min(res, f[i][k] + f[k][j] + values[i] * values[k] * values[j])\n",
    "                f[i][j] = res\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        \n",
    "        # dp[i][j]=dp[i][k]+dp[k][j]\n",
    "        # dp[i+1][j-1]+c\n",
    "        l=len(values)\n",
    "        values=values+[values[0]]\n",
    "        dp=[[0 for i in range(l)] for j in range(l)]\n",
    "        for dx in range(2,l):\n",
    "            for i in range(l):\n",
    "                j=i+dx\n",
    "                if j>=l:break\n",
    "                if dx==2:\n",
    "                    dp[i][j]=values[i]*values[i+1]*values[j]\n",
    "                else:\n",
    "                    dp[i][j]=inf\n",
    "                    for k in range(i+1,j):\n",
    "                        dp[i][j]=min(dp[i][k]+dp[k][j]+values[i]*values[j]*values[k],dp[i][j])\n",
    "        for i in dp:\n",
    "            print(i)\n",
    "        return dp[0][-1]             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        # Let dp[i][j] be min scores to triangulate the polygon values[i,j]\n",
    "        # Base case: \n",
    "        # if j - i < 2, dp[i][j] = ?\n",
    "        # dp[i][i+2] = values[i] * values[i+1] * values[i+2]\n",
    "\n",
    "        # For polygon values[i,j] where j - i > 2.\n",
    "        # Consider triangle that contains vertices values[i] and values[j].\n",
    "        # For any vertex values[k] i < k < j,\n",
    "        # triangle values[i,k,j] cuts the polygon into at most 3 parts:\n",
    "        # 1) values[i,...,k], empty if k = i + 1 (=> dp[i][j] = 0 when j - i < 2)\n",
    "        # 2) values[i,k,j]\n",
    "        # 3) values[k,...,j], empty if k = j - 1\n",
    "\n",
    "        n = len(values)\n",
    "\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        \n",
    "        for d in range(2, n):\n",
    "            # j - i = d, i + d < n\n",
    "            for i in range(n - d):\n",
    "                j = i + d\n",
    "                val = values[i] * values[j]\n",
    "                dp[i][j] = min(dp[i][k] + val * values[k] + dp[k][j] for k in range(i + 1, j))\n",
    "\n",
    "        return dp[0][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values):\n",
    "            n=len(values)\n",
    "            dp=[[0]*n for _ in range(n)]#注意这里不能设置为无穷大，因为如果为无穷大，在for循环里的计算就没有意义，值一直是无穷大\n",
    "            print(dp)\n",
    "            for i in range(n-3,-1,-1):\n",
    "                for j in range(i+2,n):\n",
    "                    res=inf\n",
    "                    for k in range(i+1,j):\n",
    "                        res=min(res,dp[i][k]+dp[k][j]+values[i]*values[j]*values[k])\n",
    "                    dp[i][j]=res            \n",
    "            print(dp)\n",
    "            return dp[0][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        length = len(values)\n",
    "\n",
    "        dp = [[float('inf') for _ in range(length)] for _ in range(length)]#i,j表示得是顺时针从i到j所能\n",
    "        for i in range(length):\n",
    "            dp[i][i] = 0\n",
    "\n",
    "        for L in range(1, length):\n",
    "            for start in range(length):\n",
    "                v_end = start + L\n",
    "                end = (v_end) % length\n",
    "                if L == 1:\n",
    "                    dp[start][end] = 0\n",
    "                    continue\n",
    "                # if v_end < length:\n",
    "                for k in range(start, end):\n",
    "                    dp[start][end] = min(dp[start][end], \\\n",
    "                    dp[start][k]+values[start] * values[k] * values[end] + dp[k][end])\n",
    "\n",
    "        \n",
    "        return dp[0][length-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "\n",
    "        '''\n",
    "        # 从第i个三角形到第j个三角形\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            # 只有两个点\n",
    "            if i + 1 == j:\n",
    "                return 0\n",
    "            if i > j:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for k in range(i + 1, j):\n",
    "                res = min(res, dfs(i, k) + dfs(k, j) + values[i] * values[k] * values[j])\n",
    "            return res\n",
    "        return dfs(0, n - 1)\n",
    "        '''\n",
    "\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 3, -1, -1):\n",
    "            # j 从 i + 2 开始，因为起码有三个点\n",
    "            for j in range(i + 2, n):\n",
    "                res = inf\n",
    "                for k in range(i + 1, j):\n",
    "                    res = min(res, f[i][k] + f[k][j] + values[i] * values[k] * values[j])\n",
    "                f[i][j] = res\n",
    "        print(f)\n",
    "        return f[0][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, A: List[int]) -> int:\n",
    "        n = len(A)\n",
    "        @lru_cache(None)\n",
    "        def helper(left, right):\n",
    "            if (left + 1) % n == right:\n",
    "                return 0\n",
    "            ans = 1000000000\n",
    "            if left < right:\n",
    "                for i in range(left + 1, right):\n",
    "                    ans = min(ans, A[left] * A[i] * A[right] + helper(left, i) + helper(i, right))\n",
    "            else:\n",
    "                for i in range(left + 1, n):\n",
    "                    ans = min(ans, A[left] * A[i] * A[right] + helper(left, i) + helper(i, right))\n",
    "                for i in range(0, right):\n",
    "                    ans = min(ans, A[left] * A[i] * A[right] + helper(left, i) + helper(i, right))\n",
    "            return ans\n",
    "\n",
    "        return min(A[a] * A[b] * A[c] + helper(a, b) + helper(b, c) + helper(c, a) for a, b, c in itertools.combinations(range(n), 3))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        m = dict()\n",
    "        def dfs(ls):\n",
    "            if tuple(ls) in m:\n",
    "        #         print(ls,len(m))\n",
    "                return m[tuple(ls)]\n",
    "            # if len(ls)==3:\n",
    "            #     m[tuple(ls)] = ls[0]*ls[1]*ls[2]\n",
    "            #     return m[tuple(ls)]\n",
    "            elif len(ls)<3:\n",
    "                return 0\n",
    "            else:\n",
    "                ress = []\n",
    "                for i in range(1,len(ls)-1):\n",
    "        #             print(ls[0:i+1],ls[i+1:])\n",
    "                    ress.append(ls[0]*ls[-1]*ls[i]+(dfs(ls[0:i+1])+dfs(ls[i:])))\n",
    "                res = min(ress)\n",
    "        #         print(tuple(ls),res,v)\n",
    "                m[tuple(ls)] = res\n",
    "                return res \n",
    "        return dfs(values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        m = dict()\n",
    "        def dfs(ls):\n",
    "            if tuple(ls) in m:\n",
    "        #         print(ls,len(m))\n",
    "                return m[tuple(ls)]\n",
    "            if len(ls)==3:\n",
    "                m[tuple(ls)] = ls[0]*ls[1]*ls[2]\n",
    "                return m[tuple(ls)]\n",
    "            elif len(ls)<3:\n",
    "                return 0\n",
    "            else:\n",
    "                ress = []\n",
    "                for i in range(1,len(ls)-1):\n",
    "        #             print(ls[0:i+1],ls[i+1:])\n",
    "                    ress.append(ls[0]*ls[-1]*ls[i]+(dfs(ls[0:i+1])+dfs(ls[i:])))\n",
    "                res = min(ress)\n",
    "        #         print(tuple(ls),res,v)\n",
    "                m[tuple(ls)] = res\n",
    "                return res \n",
    "        return dfs(values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "\n",
    "        d = {}\n",
    "\n",
    "        def helper(values):\n",
    "            if tuple(values) in d:\n",
    "                return d[tuple(values)]\n",
    "            if len(values) < 3:\n",
    "                return 0\n",
    "            if len(values) == 3:\n",
    "                d[tuple(values)] = values[0] * values[1] * values[2]\n",
    "            else:\n",
    "                res = (1<<30)\n",
    "                for i in range(1,len(values)-1):\n",
    "                    tres = values[0] * values[-1] * values[i]\n",
    "                    if tres + helper(values[:i+1]) + helper(values[i:]) < res:\n",
    "                        res = tres + helper(values[:i+1]) + helper(values[i:])\n",
    "                \n",
    "                d[tuple(values)] = res\n",
    "            \n",
    "            return d[tuple(values)]\n",
    "\n",
    "        return helper(values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        my_dfs_dict = {}\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i + 1 == j:\n",
    "                return 0\n",
    "            else:\n",
    "                my_min = 1e10\n",
    "                tmp = values[i] * values[j]\n",
    "                for k in range(i+1, j):\n",
    "                    if (i,k) not in my_dfs_dict:\n",
    "                        my_dfs_dict[(i,k)] = dfs(i, k)\n",
    "                    if (k, j) not in my_dfs_dict:\n",
    "                        my_dfs_dict[(k,j)] = dfs(k,j)\n",
    "                    my_min = min(my_min, my_dfs_dict[(i,k)]+my_dfs_dict[(k,j)]+tmp*values[k])\n",
    "                return my_min\n",
    "        return dfs(0, len(values)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        def f(values,l,r):\n",
    "            if dp[l][r]!=-1:\n",
    "                return dp[l][r]\n",
    "            ans = float('inf')\n",
    "            if l==r or l+1==r:\n",
    "                ans = 0\n",
    "            else:\n",
    "                for m in range(l+1,r):\n",
    "                    ans = min(ans,f(values,l,m)+f(values,m,r)+values[l]*values[r]*values[m])\n",
    "            dp[l][r] = ans\n",
    "            return ans\n",
    "        n = len(values)\n",
    "        dp = [[-1]*n for _ in range(n)]\n",
    "        return f(values,0,n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "\n",
    "        # @cache\n",
    "        memo = [[-1]*len(values) for _ in range(len(values))]\n",
    "        def dp(i,j):\n",
    "            if i == j-1:\n",
    "                return 0\n",
    "            if memo[i][j] != -1: return memo[i][j]\n",
    "            res = inf\n",
    "            for k in range(i+1,j):\n",
    "                res = min(res, dp(i, k) + dp(k, j) + values[i]*values[j]*values[k])\n",
    "            memo[i][j] = res\n",
    "            return res\n",
    "        return dp(0, len(values)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        由顶点i开始到顶点j结束的若干个顶点组成的多边形的最小剖分结果\n",
    "        \"\"\"\n",
    "        def dp(i: int, j: int):\n",
    "            # 数组中已存储结果，直接返回\n",
    "            if memory[i][j] is not None:\n",
    "                return memory[i][j]\n",
    "            if j < i + 2:\n",
    "                # 只有两个顶点，不构成多边形，结果为0\n",
    "                value = 0\n",
    "            else:\n",
    "                value = sys.maxsize     # 初始化最小剖分结果\n",
    "                # 枚举起始顶点i和终止顶点j之间的所有顶点k，作为拆分点\n",
    "                for k in range(i+1, j):\n",
    "                    value = min(value, dp(i, k) + values[i] * values[k] * values[j] + dp(k, j))\n",
    "            \n",
    "            memory[i][j] = value    # 存储结果\n",
    "            return value\n",
    "\n",
    "        n = len(values)     # 获取顶点个数\n",
    "        memory = [[None for _ in range(n)] for _ in range(n)]   # 二维数组，存储由顶点i开始到顶点j结束的若干个顶点组成的多边形的最小剖分结果；初始化值为None从而判断对应顶点区间是否处理过\n",
    "        return dp(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        # triangle that uses A[0], A[n - 1]\n",
    "        # dp[0][n - 1] = dp[0 : k] + dp[k : n - 1] + val[0] * val[n - 1] * val [k]\n",
    "        n = len(values)\n",
    "        dp = [[sys.maxsize] * n for _ in range(n)]\n",
    "        \n",
    "        # initialization\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 0\n",
    "        \n",
    "        for i in range(n - 1):\n",
    "            dp[i][i + 1] = 0\n",
    "\n",
    "        for l in range(3, n + 1):\n",
    "            for i in range(0, n - l + 1):\n",
    "                j = i + l - 1\n",
    "                print((i, j))\n",
    "                for k in range(i, j):\n",
    "                    print((i, j, k))\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k])\n",
    "        print(dp)\n",
    "        return dp[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n=len(values)\n",
    "        f=[[-1 for i in range(n)] for i in range(n)]\n",
    "        def dp(i, j):\n",
    "            if f[i][j]!=-1:\n",
    "                return f[i][j]\n",
    "            if i + 2 > j:\n",
    "                f[i][j]=0\n",
    "                return 0\n",
    "            if i + 2 == j:\n",
    "                f[i][j]=values[i] * values[i + 1] * values[j]\n",
    "                return f[i][j]\n",
    "            \n",
    "            f[i][j] = min((values[i] * values[k] * values[j] + dp(i, k) + dp(k, j)) for k in range(i + 1, j))\n",
    "            return f[i][j]\n",
    "        return dp(0, n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n=len(values)\n",
    "        # dp=[[0]*n for _ in range(n)]\n",
    "        # for i in range(n-3,-1,-1):\n",
    "        #     for j in range(i+2,n):\n",
    "        #         res=inf\n",
    "        #         for k in range(i+1,j):\n",
    "        #             res=min(res,dp[i][k]+dp[k][j]+values[i]*values[j]*values[k])\n",
    "        #         dp[i][j]=res\n",
    "\n",
    "        # print(dp)\n",
    "        # return dp[0][-1]\n",
    "\n",
    "\n",
    "        # @cache\n",
    "        cache=[[-1]*n for _ in range(n)]\n",
    "        def dfs(i,j):\n",
    "            if i+1==j:\n",
    "                return 0\n",
    "            if cache[i][j]!=-1:\n",
    "                return cache[i][j]\n",
    "            res=inf\n",
    "            for k in range(i+1,j):\n",
    "                res=min(res,dfs(i,k)+dfs(k,j)+values[i]*values[j]*values[k])\n",
    "            cache[i][j]=res\n",
    "            return res\n",
    "        return dfs(0,n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        dp = [[float('inf')] * n for _ in range(n)]\n",
    "        \n",
    "        def helper(i: int, j: int) -> int:\n",
    "            if j - i < 2:\n",
    "                return 0\n",
    "            if dp[i][j] != float('inf'):\n",
    "                return dp[i][j]\n",
    "            \n",
    "            for k in range(i+1, j):\n",
    "                dp[i][j] = min(dp[i][j], helper(i, k) + helper(k, j) + values[i] * values[k] * values[j])\n",
    "            \n",
    "            return dp[i][j]\n",
    "        \n",
    "        return helper(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values):\n",
    "        result_map = {}\n",
    "        def dp(l, r):\n",
    "            if r - l < 2:\n",
    "                return 0\n",
    "            elif r - l == 2:\n",
    "                return values[l] * values[l + 1] * values[r]\n",
    "            else:\n",
    "                key = '{}:{}'.format(l, r)\n",
    "                if key in result_map:\n",
    "                    return result_map[key]\n",
    "                result = min((values[l] * values[r] * values[m] + dp(l, m) + dp(m, r) for m in range(l + 1, r)))\n",
    "                result_map[key] = result\n",
    "                return result\n",
    "        return dp(0, len(values) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(arr):\n",
    "            n = len(arr)\n",
    "            if n == 3:\n",
    "                return arr[0] * arr[1] * arr[2]\n",
    "            res = float(\"inf\")\n",
    "            for i in range(1, n - 1):\n",
    "                tmp = arr[0] * arr[i] * arr[n - 1]\n",
    "                if i > 1:\n",
    "                    tmp += dfs(arr[:i + 1])\n",
    "                if i < n - 2:\n",
    "                    tmp += dfs(arr[i:])\n",
    "                res = min(res, tmp)\n",
    "            \n",
    "            return res\n",
    "\n",
    "        return dfs(tuple(values))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        self.values = values\n",
    "        n = len(values)\n",
    "        return self.dfs(0, n-1)\n",
    "\n",
    "    @cache\n",
    "    def dfs(self, i, j):\n",
    "        if j - i <=1:\n",
    "            return 0\n",
    "        res = inf\n",
    "\n",
    "        for k in range(i+1, j):\n",
    "            res = min(res, self.dfs(i,k)+ self.dfs(k,j) + self.values[i]*self.values[j]*self.values[k])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, v: List[int]) -> int:\n",
    "        ans = inf\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i + 1 == j:\n",
    "                 return 0  # 只有两个点，无法组成三角形\n",
    "            nonlocal ans\n",
    "            for k in range(i + 1, j):\n",
    "                ans = min(ans,dfs(i, k) + dfs(k, j) + v[i] * v[j] * v[k])\n",
    "            return ans\n",
    "        return dfs(0, len(v) - 1)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, v: List[int]) -> int:\n",
    "        n=len(v)\n",
    "        \n",
    "    \n",
    "        @cache\n",
    "        def dfs(i:int,j:int) -> int:\n",
    "            if i+1==j:\n",
    "                return 0\n",
    "                \n",
    "            return min([dfs(i,k) +dfs(k,j)+v[i]*v[j]*v[k] for k in range(i+1,j)])\n",
    "         \n",
    "         \n",
    "        \n",
    "        return dfs(0,n-1)\n",
    "            \n",
    "            \n",
    "           \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(A):\n",
    "            n = len(A)\n",
    "            if n<3:\n",
    "                return 0\n",
    "            return min(A[0]*A[-1]*A[i]+dfs(A[:i+1])+dfs(A[i:]) for i in range(1, n-1))\n",
    "        return dfs(tuple(values))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(A):\n",
    "            n = len(A)\n",
    "            if n<3:\n",
    "                return 0\n",
    "            return min(A[0]*A[-1]*A[i]+dfs(A[:i+1])+dfs(A[i:]) for i in range(1, n-1))\n",
    "        return dfs(tuple(values))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, v: List[int]) -> int:\n",
    "        n = len(v)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i : int,j : int) -> int:\n",
    "            if i + 1 == j:\n",
    "                return 0\n",
    "\n",
    "            return min([dfs(i,k) + dfs(k,j) + v[i] * v[j] * v[k] for k in range(i + 1,j)])\n",
    "\n",
    "\n",
    "        return dfs(0,n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        @lru_cache(maxsize = None)\n",
    "        def dp(i, j):\n",
    "            if i + 2 > j:\n",
    "                return 0\n",
    "            if i + 2 == j:\n",
    "                return values[i] * values[i + 1] * values[j]\n",
    "            return min((values[i] * values[k] * values[j] + dp(i, k) + dp(k, j)) for k in range(i + 1, j))\n",
    "        return dp(0, len(values) - 1)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i + 1 == j: return 0\n",
    "            return min(dfs(i, k) + dfs(k, j) + values[i] * values[j] * values[k] for k in range(i + 1, j))\n",
    "        return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, v: List[int]) -> int:\n",
    "        n=len(v)\n",
    "        @cache  \n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i + 1 == j: return 0  # i->j的多变形:只有两个点，无法组成三角形\n",
    "            res=inf\n",
    "            for k in range(i+1, j):#枚举顶点 k\n",
    "                res=min(res,dfs(i, k) + dfs(k, j) + v[i] * v[j] * v[k]) #【核心】拆分成三个部分\n",
    "            return res               \n",
    "        return dfs(0, len(v) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            if(i+2 > j):\n",
    "                return 0\n",
    "            if(i+2 == j):\n",
    "                return values[i]*values[i+1]*values[i+2]\n",
    "            res = float('inf')\n",
    "            for k in range(i+1,j):\n",
    "                res = min(res, values[i]*values[k]*values[j] + dp(i,k) + dp(k,j))\n",
    "            return res\n",
    "        return dp(0, len(values)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: list[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(start, end):\n",
    "            if end - start + 1 < 3:\n",
    "                return 0\n",
    "            else:\n",
    "                return min(values[start] * values[end] * values[i] + \\\n",
    "                           dfs(start, i) + dfs(i, end) for i in range(start + 1, end))\n",
    "\n",
    "        n = len(values)\n",
    "        return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j == i+1:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for k in range(i+1, j):\n",
    "                ans = min(ans, dfs(i,k)+dfs(k,j) + values[i]*values[k]*values[j])\n",
    "            return ans\n",
    "        return dfs(0, len(values)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        #dp[i][j]表示i到j(顺时针，只考虑顺时针,j比i大)，然后ij走一条边得到的多边形的最低分数和\n",
    "        size=len(values)\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i+1==j:\n",
    "                return 0\n",
    "            return min([dfs(i,k)+dfs(k,j)+values[i]*values[j]*values[k] for k in range(i+1,j)])\n",
    "        return dfs(0,size-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(i,j):\n",
    "            if i + 2 > j:\n",
    "                return 0\n",
    "            if i + 2 == j:\n",
    "                return values[i] * values[i+1]* values[j]\n",
    "            return min(values[i]*values[k]*values[j] + dp(i,k)+ dp(k,j) for k in range(i+1,j))\n",
    "        return dp(0 ,len(values) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            if i + 2 > j:\n",
    "                return 0\n",
    "            if i + 2 == j:\n",
    "                return values[i] * values[j] * values[i + 1]\n",
    "            return min((values[i] * values[k] * values[j] + dp(i, k) + dp(k, j)) for k in range(i + 1, j))\n",
    "        return dp(0, len(values) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if j == i+1:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for k in range(i+1,j):\n",
    "                 res = min(res, dfs(i,k)+dfs(k,j)+values[i]*values[j]*values[k])\n",
    "            return res\n",
    "        return  dfs(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if abs(i-j) < 2:\n",
    "                return 0\n",
    "\n",
    "            # :\n",
    "            # res = inf\n",
    "            # for k in range(i+1, j):\n",
    "            #     res = min(dfs(i, k) + dfs(k, j) + values[i]*values[j]*values[k], res)\n",
    "\n",
    "            # return res\n",
    "            return min((dfs(i, k) + dfs(k, j) + values[i]*values[j]*values[k]) for k in range(i+1, j))\n",
    "\n",
    "        return dfs(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if j-i<2:\n",
    "                return 0\n",
    "            res = inf # 后面取min，因此这里初始化我饿正无穷\n",
    "            for k in range(i+1,j):\n",
    "                res = min(res, dfs(i,k)+dfs(k,j)+values[i]*values[k]*values[j]) # 这个values[i]*values[k]*values[j]必须加在这一行，不可以在return行，因为k会变化\n",
    "            return res\n",
    "        return dfs(0,n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i+1==j:\n",
    "                return 0\n",
    "            return min(dfs(i,k)+dfs(k,j)+values[i]*values[k]*values[j] for k in range(i+1,j))\n",
    "        return dfs(0,len(values)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, v: List[int]) -> int:\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i + 1 == j: return 0  # 只有两个点，无法组成三角形\n",
    "            return min(dfs(i, k) + dfs(k, j) + v[i] * v[j] * v[k]\n",
    "                       for k in range(i + 1, j))  # 枚举顶点 k\n",
    "        return dfs(0, len(v) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        # n = len(values)\n",
    "        # dp = [[0]*n for _ in range(n)] #\n",
    "        # i<k,i倒叙，j正序\n",
    "        # for i in range(n-3,-1,-1):\n",
    "        #     for j in range(i+2,n):\n",
    "        #         res = inf\n",
    "        #         for k in range(i+1,j):#i+= k and k+1=j需要返回0，所以不能置为inf\n",
    "        #             res = min(res,dp[i][k]+values[i]*values[k]*values[j]+dp[k][j])\n",
    "        #             # print(res)\n",
    "        #         dp[i][j] = res \n",
    "        # # print(dp)\n",
    "        # return dp[0][n-1] \n",
    "\n",
    "\n",
    "\n",
    "        n = len(values)\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i,j):\n",
    "            \n",
    "            if i+1 == j:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for k in range(i+1,j):\n",
    "                res = min(res,dfs(i, k)+dfs(k, j)+values[i]*values[k]*values[j])\n",
    "            return res \n",
    "\n",
    "        return dfs(0, n-1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == j or i + 1 == j:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for k in range(i + 1, j):\n",
    "                ans = min(ans, dfs(i, k) + dfs(k, j) + values[i] * values[j] * values[k])\n",
    "            return ans\n",
    "        return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            if i + 2 > j:\n",
    "                return 0\n",
    "            if i + 2 == j:\n",
    "                return values[i] * values[i + 1] * values[j]\n",
    "            return min((values[i] * values[k] * values[j] + dp(i, k) + dp(k, j)) for k in range(i + 1, j))\n",
    "        return dp(0, len(values) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "\n",
    "        n = len(values)\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            if l == r - 1:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for k in range(l + 1, r):\n",
    "                res = min(res, dfs(l, k) + dfs(k, r) + values[l] * values[r] * values[k])\n",
    "            return res\n",
    "        return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i+1==j:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for k in range(i+1,j):\n",
    "                ans = min(ans, dfs(i,k)+dfs(k,j)+values[i]*values[k]*values[j])\n",
    "            return ans\n",
    "        return dfs(0,len(values)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        @cache\n",
    "        def dfs(i,j): # 默认i<k<j\n",
    "            if j-i == 1:\n",
    "                return 0 # 这里又错写成inf 哎\n",
    "            ans = inf #注意初始化边界条件 之前写错成0了\n",
    "            for k in range(i+1,j):\n",
    "                ans = min(ans,values[i]* values[j]* values[k] + dfs(i,k)+dfs(k,j))\n",
    "            return ans\n",
    "\n",
    "        return dfs(0,n-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i + 1 == j:\n",
    "                return 0\n",
    "\n",
    "            res = inf\n",
    "            for k in range(i + 1, j):\n",
    "                res = min(res, dfs(i, k) + dfs(k, j) + values[i] * values[j] * values[k])\n",
    "\n",
    "            return res\n",
    "\n",
    "        return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            if i + 2 > j:\n",
    "                return 0\n",
    "            if i + 2 == j:\n",
    "                return values[i] * values[i + 1] * values[j]\n",
    "            return min((values[i] * values[k] * values[j] + dp(i, k) + dp(k, j)) for k in range(i + 1, j))\n",
    "        return dp(0, len(values) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScoreTriangulation(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i + 1 == j:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for k in range(i + 1, j):\n",
    "                res = min(res, dfs(k, j) + dfs(i, k) + values[i] * values[k] * values[j])\n",
    "\n",
    "            return res\n",
    "\n",
    "        return dfs(0, n - 1)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
